
#include "huffman.h"

/**
 *  功  能：
 *      霍夫曼树的数组权值最小两个节点的下标
 *  参  数：
 *      htree  ：输入，霍夫曼树
 *      num    ：输入，霍夫曼树数组中有效节点的个数
 *      index1 ：输出，权值最小的节点的下标
 *      index2 ：输出，权值次小的节点的下标
 *  返回值：
 *      无
 **/
static void select_minimum_index(huffmanTree *htree, unsigned int num, unsigned int *index1, unsigned int *index2)
{
    unsigned int i = 1;
    // 记录最小权值所在的下标
    unsigned int indexMin;
    if (htree == NULL || index1 == NULL || index2 == NULL)
        goto END;

    // 遍历目前全部节点，找出最前面第一个没有被构建的节点
    while (i <= num && (htree + i)->parent != 0)
        i++;

    indexMin = i;

    //继续遍历全部结点，找出权值最小的单节点
    while (i <= num)
    {
        // 如果节点没有被构建，并且此节点的的权值比 下标为目前记录的下标的节点的权值小
        if ((htree + i)->parent == 0 && (htree + i)->weight < (htree + indexMin)->weight)
            indexMin = i; // 找到了最小权值的节点，下标为i
        i++;
    }
    *index1 = indexMin; // 最小的节点已经找到了，下标为 indexMin

    // 开始查找次小权值的下标
    i = 1;
    while (i <= num)
    {
        // 找出下一个没有被构建的节点，且没有被 index1 指向
        if ((htree + i)->parent == 0 && i != (*index1))
            break;
        i++;
    }
    indexMin = i;

    // 继续遍历全部结点，找到权值次小的那一个
    i = 1;
    while (i <= num)
    {
        if ((htree + i)->parent == 0 && i != (*index1))
        {
            // 如果此结点的权值比 indexMin 位置的节点的权值小
            if ((htree + i)->weight < (htree + indexMin)->weight)
                indexMin = i;
        }
        i++;
    }
    // 次小的节点已经找到了，下标为 indexMin
    *index2 = indexMin;

END:
    return;
}

/**
 *  功  能：
 *      打印输出霍夫曼树的各个节点之间的关系
 *  参  数：
 *      hTree ：输入，霍夫曼树
 *      num   ：输入，霍夫曼树数组中有效节点的个数
 *  返回值：
 *      无
 **/
void print_huffman_Numbers(huffmanTree *hTree, unsigned int num)
{
    printf("\nThe node relationship of the Huffman tree is:\n");
    printf("\n\t| index | weight | parent | lchilf | rchild |\n");

    for (unsigned int i = 0; i < num; i++)
    {
        printf("\t|%4d   |%7d |%7d |%7d |%7d |\n", i, hTree[i].weight, hTree[i].parent, hTree[i].lchild, hTree[i].rchild);
    }
    putchar(10);
}
/**
 *  功  能：
 *      创建一个霍夫曼树
 *  参  数：
 *      weight ：保存权值的数组
 *      num    ：权值数组的长度，也就是权值的个数 
 *  返回值：
 *      成功 ：创建成功的霍夫曼树的首地址
 *      失败 ：NULL
 **/
huffmanTree *Create_huffmanTree(unsigned int *weight, unsigned int num)
{
    huffmanTree *hTree = NULL;
    if (weight == NULL || num <= 1) // 如果只有一个编码就相当于0
        goto END;

    hTree = (huffmanTree *)malloc((2 * num - 1 + 1) * sizeof(htNode)); // 0号下标预留。用来表示初始化的状态，所以要在原来的基础上加1
    if (hTree == NULL)
        goto END;

    // 初始化哈夫曼树中的所有结点，均初始化为0
    memset(hTree, 0, (2 * num - 1 + 1) * sizeof(htNode));
    // 将权值赋值成传入的权值，并且从数组的第二个位置开始，i=1
    for (unsigned int i = 1; i <= num; i++)
        (hTree + i)->weight = *(weight + i - 1);

    // 构建哈夫曼树，将新创建的节点在原本节点的后边，从num+1开始
    for (unsigned int offset = num + 1; offset < 2 * num; offset++)
    {
        unsigned int index1, index2;
        select_minimum_index(hTree, offset - 1, &index1, &index2); // 获取权值最小的节点的下标

        // printf("index1 = %d, index2 = %d, hTree[1] = %d, hTree[2] = %d\n",
        //        index1, index2, hTree[index1].weight, hTree[index2].weight);

        (hTree + offset)->weight = (hTree + index1)->weight +
                                   (hTree + index2)->weight; // 将权值最小的两个节点的权值相加醉成新节点的权值
        (hTree + index1)->parent = offset;                   // 权值最小的节点的双亲结点为此新节点
        (hTree + index2)->parent = offset;                   // 值次小的节点的双亲结点为此新节点
        (hTree + offset)->lchild = index1;                   // 此新节点的左孩子为权值最小的节点
        (hTree + offset)->rchild = index2;                   // 此新节点的右孩子为权值次小的节点
    }

END:
    return hTree;
}

/**
 *  功  能：
 *      销毁一个霍夫曼树
 *  参  数：
 *      htree ：要销毁的霍夫曼树
 *  返回值：
 *      无
 **/
void Destory_huffmanTree(huffmanTree *htree)
{
    if (htree != NULL)
        free(htree);
    htree = NULL;
}

/**
 *  功  能：
 *       查询/计算在特定霍夫曼树下的对应圈权值的霍夫曼编码
 *  参  数：
 *      htree ：参考的霍夫曼树
 *      nums  ：原本权值的个数
 *      weight：权值
 *  返回值：
 *      成功：返回权值weight对应的编码
 *      失败：NULL
 **/
huffmanCode *Create_HuffmanCode_One(huffmanTree *htree, unsigned int nums, unsigned int weight)
{
    huffmanCode *hCode = NULL, *tmpCode = NULL;
    unsigned int i = 0, index = 0, parent = 0;

    if (htree == NULL || weight < 1)
        goto END;

    // 找到权值匹配的数组的下标
    while (htree[i].weight != weight && i <= nums)
        i++;
    if (i > nums) // 如果成立，额说明没有找到对应的权值，是为假权值
        goto END;

    tmpCode = (char *)malloc(sizeof(char) * nums);
    if (tmpCode == NULL)
        goto END;

    memset(tmpCode, 0, sizeof(char) * nums);
    // 霍夫曼编码的起始点，一般情况来说，最长的编码的长度为权值个数-1
    index = nums - 1;
    //从叶子到根结点求编码
    parent = (htree + i)->parent;
    while (parent != 0)
    {
        if ((htree + parent)->lchild == (unsigned int)i) //从右到左的顺序编码入数组内
            tmpCode[--index] = '0';                      //左分支标0
        else
            tmpCode[--index] = '1'; //右分支标1

        i = parent;
        parent = (htree + parent)->parent; //由双亲节点向霍夫曼树的根节点移动
    }

    hCode = (char *)malloc((nums - index) * sizeof(char)); //字符串，需要以'\0'为结束
    if (hCode == NULL)
        goto END;

    memset(hCode, 0, (nums - index) * sizeof(char));
    strcpy(hCode, &tmpCode[index]);

END:
    if (tmpCode != NULL)
        free(tmpCode);
    tmpCode = NULL;

    return hCode;
}

/**
 *  功  能：
 *       霍夫曼编码
 *  参  数：
 *      htree ：要销毁的霍夫曼树
 *  返回值：
 *      无
 **/
huffmanCode **Create_HuffmanCode_All(huffmanTree *htree, unsigned int num)
{
    huffmanCode **ret = NULL;
    unsigned int i = 0;

    ret = (huffmanCode **)malloc(sizeof(char *) * num);
    if (ret == NULL)
        goto END;
    memset(ret, 0, sizeof(char *) * num);

    for (i = 0; i < num; i++)
    {
        ret[i] = Create_HuffmanCode_One(htree, num, htree[i + 1].weight);
        // printf("htree[%d].weight = %d, ret[%d] = %s\n", i + 1, htree[i + 1].weight, i, ret[i]);
    }
    // 将霍夫曼的最后一个位置设置为NULL，便于单独进行遍历等操作
    ret[i] = (huffmanCode *)malloc(sizeof(char *));
    ret[i] = NULL;

END:
    return ret;
}

/**
 *  功  能：
 *      销毁一个霍夫曼编码
 *  参  数：
 *      hcode ：要销毁的霍夫曼编码
 *  返回值：
 *      无
 **/
void Destory_huffmanCode(huffmanCode **hcode)
{
    int i = 0;
    while (hcode[i] != NULL)
    {
        free(hcode[i]);
        hcode[i] = NULL;
        i++;
    }

    free(hcode[i]);
    hcode[i] = NULL;

    if (hcode != NULL)
        free(hcode);
    hcode = NULL;
}

/**
 *  功  能：
 *      打印输出各个权值对应的霍夫曼编码之间的关系
 *  参  数：
 *      hcode  ：输入，霍夫曼编码表 
 *  返回值：
 *      无
 **/
void print_huffman_Coding(huffmanCode **hcode)
{
    int i = 0;
    printf("The Huffman coding table is:\n\n");
    printf("\t| index | hcode |\n");
    while (hcode[i] != NULL)
    {
        printf("\t|%4d   |  %s", i, hcode[i]);
        for (unsigned int j = 0; j < 5 - strlen(hcode[i]); j++)
            printf(" ");
        printf("|\n");
        i++;
    }
    printf("\t|%4d   |  null |\n\n", i);
}

/**
 *  功  能：
 *      将字符串进行霍夫曼编码
 *  参  数：
 *      hcode ：输入，霍夫曼编码表 
 *      chars : 输入，与权值一一对应的字符表
 *      num   : 输入，权值的个数
 *      str   : 输入，要装换的字符串
 *  返回值：
 *      成功 ：0
 *      失败 ：-1
 *  说  明：
 *      如果在字符码表 chars 中没有找到字符串 str 中的字符，则在返回的字符串中用 ‘-’ 替代
 **/
int String_to_huffmanCoding(huffmanCode **hcode, char chars[], unsigned int num, char *str, char **out)
{
    unsigned int i;
    char *temp = NULL;
    int ret = -1;
    if (hcode == NULL || *hcode == NULL || chars == NULL || str == NULL || out == NULL)
        goto END;

    // 一般情况下，有多少个权值的话其中编码最长的长度也就是权值的个数
    temp = (char *)malloc((sizeof(char) * num) * num);
    if (temp == NULL)
        goto END;
    memset(temp, 0, (sizeof(char) * num) * num);

    while (*str != '\0')
    {
        for (i = 0; i < num; i++) // 在字符串中查找与取值匹配的字符表中的匹配的项
        {
            if (*str == chars[i]) // 字符串的字符和字符表中匹配到，干完活后立即退出本次循环
            {
                strcat(temp, hcode[i]);
                break;
            }
        }
        if (i >= num) // 说明有字符在字符表中没有找到
        {
            strcat(temp, "-");
        }
        str++;
    }

    *out = (char *)malloc(sizeof(char) * (strlen(temp) + 1));
    memset(*out, 0, sizeof(char) * (strlen(temp) + 1));
    if (*out == NULL)
        goto END;
    // 赋值
    strcpy(*out, temp);
    ret = 0;
END:
    free(temp);
    temp = NULL;

    return ret;
}

/**
 *  功  能：
 *      将霍夫曼编码转换为字符串 -- 解码
 *  参  数：
 *      htree ：输入，霍夫曼树 
 *      chars : 输入，与权值一一对应的字符表
 *      num   : 输入，权值的个数
 *      code  : 输入，要转换的霍夫曼编码
 *      out   ：解密后的字符串输出
 *  返回值：
 *      成功 ：0
 *      失败 ：-1
 *  说  明：
 *      如果在字符码表 chars 中没有找到编码字符串 code 中的对应的字符，则在返回的字符串中用 ‘-’ 替代
 **/
int huffmanCoding_to_String(huffmanTree *htree, char chars[], unsigned int nums, char *code, char **out)
{
    int i = 1;
    unsigned int p;
    int ret = -1;
    char *tmpCode = NULL;
    if (htree == NULL || chars == NULL || nums < 1 || code == NULL || out == NULL)
    {
        ret = -1;
        goto END;
    }

    p = htree[i].parent;

    tmpCode = (char *)malloc(sizeof(char) * nums);
    if (tmpCode == NULL)
        goto END;
    memset(tmpCode, 0, sizeof(char) * nums);

    // 找到那个 parent 字段为 0 的节点，他就是这个霍夫曼树的根节点
    while (htree[p].parent != 0)
        p = htree[p].parent;
    // 将根节点的下标记录下来
    ret = p;

    i = 0;
    // 直到左孩子为0，右孩子为0
    while (*code != '\0')
    {
        while (htree[p].lchild != 0 && htree[p].rchild != 0 && *code != '\0')
        {
            if (*code == '0') // 找左子树
                p = htree[p].lchild;
            else if (*code == '1') // 找右子树
                p = htree[p].rchild;
            else // 编码异常printf("code Error!\n");
                goto END;

            code++;
        }
        if (*code == '\0' && p > nums) // 有没有识别的编码
            tmpCode[i++] = '-';
        else
            tmpCode[i++] = chars[p - 1];

        p = ret;
    }

    *out = (char *)malloc(sizeof(char) * (strlen(tmpCode) + 1));
    memset(*out, 0, sizeof(char) * (strlen(tmpCode) + 1));
    strcat(*out, tmpCode);

    free(tmpCode);
    tmpCode = NULL;

    ret = 0;
END:
    return ret;
}

func_huffmanTree fhuffmanTree = {
    Create_huffmanTree,
    print_huffman_Numbers,
    Destory_huffmanTree,
    Create_HuffmanCode_One,
    Create_HuffmanCode_All,
    Destory_huffmanCode,
    print_huffman_Coding,
    String_to_huffmanCoding,
    huffmanCoding_to_String};
